package ustc.xiaoyang.karl.simulation;

import java.util.ArrayList;
import java.util.List;

/**
 * 螺旋矩阵 54
 * 使用标记法解决
 */
public class SpiralMatrix54 {
    public static void main(String[] args) {
        int[][] matrix = {{1,2,3},{4,5,6},{7,8,9}};
        System.out.println(new SpiralMatrix54().spiralOrder(matrix));
    }
    private final int[][] DIR = {{0,1},{1,0},{0,-1},{-1,0}};

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        int m = matrix.length;
        int n = matrix[0].length;
        int i = 0;
        int j = 0;
        int dir = 0;
        for (int k = 0; k < m*n; k++) {
            ans.add(matrix[i][j]);
            matrix[i][j] = Integer.MAX_VALUE;
            int x = i + DIR[dir][0];
            int y = j + DIR[dir][1];
            if(x<0 || x>=m || y<0 || y>=n || matrix[x][y] == Integer.MAX_VALUE)
                dir = (dir+1)%4;
            i = i + DIR[dir][0];
            j = j + DIR[dir][1];
        }
        return ans;


    }
}
